/**
 * Created with IntelliJ IDEA.
 *
 * @Auther: 邹陆川
 * @Date: 2022/04/19/1:13 下午
 * @Description:快速排序
 * 核心思想：递归调用分好组的元素，
 * 设定一个初始基准值（一般设为数组的第一个元素）
 * 定义两个指针，一个从最右边，一个指向最左边
 * 先让最右边的指针往左边走（自减）遇到比基准值小的就停下
 * 然后让左边的指针往右边走（自增）遇到比基准值大的就停下
 * 交换两边指针的值
 * 当两边指针相遇，则交换基准值和他们相遇的点
 * 左右递归调用排序
 * 出口为左边大于右边
 *
 *
 *
 * 时间复杂度：O=(nlogn)
 *
 */
public class QuickSort {
  static void sort(Integer[] arr,int left,int right){
    //出口
    if(left > right){
      return;
    }
    //定义变量
    int l = left,r = right;
    //定义初始基准值为下标left的值
    int temp = arr[l];

    //遍历
    while(l < r){
      //先让右边的指针往左走 --
      while (l < r  && temp <= arr[r]){
        r --;
      }
      //再让左边的指针往右走（既++）
      while(l < r  && temp >= arr[l]){
        l ++;
      }
      //走到这里说明他们不满足条件了，需要交换
      if(l < r){
        int a = arr[l];
        arr[l] = arr[r];
        arr[r] = a;
      }
    }
    //最后将基准为与i和j相等位置的数字交换
    arr[left] = arr[l];
    arr[l] = temp;
    //递归调用左半数组
    sort(arr, left, r-1);
    //递归调用右半数组
    sort(arr, r+1, right);
  }
}
